#!/usr/bin/python
# -*- coding: utf8 -*-

from math import sqrt

a = (1+sqrt(5))/2

def recur(n):
    # 递归结束条件
    if(n == 0):
        return 1
    elif(n == 1):
        return a
    else:
        b = recur(n/2)  #递归调用,Divide and Conquer
        # Combine
        b = b * b
        if(n % 2 == 1):  #处理n为奇数的情况
            b = b * a
        return b

def fib(n):
    """ F(n) = ((1+sqrt(5))/2)^n/sqrt(5)  """
    if(n == 0):
        return 0
    elif(n == 1):
        return 1
    else:
        return round(recur(n)/sqrt(5))
